#pragma once

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
namespace YX
{
	template<class W>
	struct BinaryTreeNode
	{
		struct BinaryTreeNode<W>* _left;
		struct BinaryTreeNode<W>* _right;

		W _data;

		BinaryTreeNode(const W& data)
			:_left(nullptr)
			,_right(nullptr)
			,_data(data)
		{

		}
	};

	template<class W>
	class BinaryTree
	{
		typedef BinaryTreeNode<W> Node;
	private:
		Node* _root=nullptr;

		Node* _Create(const vector<W>& v, const W& w, int& index)
		{
			if (v[index] == w)
			{
				index++;
				return nullptr;
			}

			Node* newNode = new Node(v[index]);
			index++;

			newNode->_left = _Create(v, w, index);
			newNode->_right = _Create(v, w, index);

			return newNode;
		}

		void _Destroy(Node* root)
		{
			if (root == nullptr)
				return;
			_Destroy(root->_left);
			_Destroy(root->_right);

			delete root;
		}

		void _PrevOrder(Node* root)
		{
			if (root == nullptr)
			{
				cout << '#' << " ";
				return;
			}

			cout << root->_data << " ";
			_PrevOrder(root->_left);
			_PrevOrder(root->_right);
		}

		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				cout << '#' << " ";
				return;
			}

			_InOrder(root->_left);
			cout << root->_data << " ";
			_InOrder(root->_right);
		}

		void _PostOrder(Node* root)
		{
			if (root == nullptr)
			{
				cout << '#' << " ";
				return;
			}

			_PostOrder(root->_left);
			_PostOrder(root->_right);
			cout << root->_data << " ";

		}

		Node* _Copy(Node* root)
		{
			if (root == nullptr)
			{
				return nullptr;
			}

			Node* newNode = new Node(root->_data);
			newNode->_left = _Copy(root->_left);
			newNode->_right = _Copy(root->_right);

			return newNode;
		}

	public:
		BinaryTree() = default;

		BinaryTree(const vector<W>& v, const W& w)
			:_root(nullptr)
		{
			int index = 0;
			_root = _Create(v, w, index);
		}

		~BinaryTree()
		{
			if (_root != nullptr)
			{
				_Destroy(_root);
				_root = nullptr;
			}
		}

		BinaryTree(const BinaryTree<W>& tree)
			:_root(nullptr)
		{
			_root = _Copy(tree._root);
		}

		BinaryTree<W>& operator=(BinaryTree<W> tree)
		{
			std::swap(_root, tree._root);
			return *this;
		}

		void PrevOrder()
		{
			_PrevOrder(_root);
			std::cout << std::endl;
		}

		void InOrder()
		{
			_InOrder(_root);
			std::cout << std::endl;
		}

		void PostOrder()
		{
			_PostOrder(_root);
			std::cout << std::endl;
		}

		void LevelOrder()
		{
			if (_root == nullptr)
				return;

			queue<Node*> q;
			q.push(_root);

			while (!q.empty())
			{
				Node* front = q.front();
				q.pop();
				cout << front->_data << " ";

				if (front->_left)
				{
					q.push(front->_left);
				}

				if (front->_right)
				{
					q.push(front->_right);
				}
			}
			cout << endl;
		}

		bool IsComplete()
		{
			queue<Node*> q;
			q.push(_root);

			while (!q.empty())
			{
				Node* front = q.front();
				q.pop();

				if (front == nullptr)
				{
					break;
				}

				q.push(front->_left);
				q.push(front->_right);
			}

			while (!q.empty())
			{
				Node* front = q.front();
				q.pop();

				if (front != nullptr)
				{
					return false;
				}
			}

			return true;
		}
	};

}